#pragma once 

#include <memory>
#include <mutex>
#include <list>
#include <unordered_map>


/* *************************************** 缓存策略基类 *************************************** */
template <typename Key, typename Value>
class CachePolicy
{
public:
    virtual ~CachePolicy() {};

    // 添加缓存接口
    virtual void put(Key key, Value value) = 0;

    // key是传入参数  访问到的值以传出参数的形式返回 | 访问成功返回true
    virtual bool get(Key key, Value& value) = 0;
    
    // 如果缓存中能找到key，则直接返回value
    virtual Value get(Key key) = 0;

};



// 前向声明
template<typename Key, typename Value> class LruCache;

/* ************************************* LRU缓存链表的节点 ************************************* */
template<typename Key, typename Value>
class LruNode 
{
friend class LruCache<Key, Value>;

public:
    LruNode(Key key, Value value)
        : m_key(key)
        , m_value(value)
        , m_accessCount(1) 
    {} 

    // 提供必要的访问器
    Key getKey() const { return m_key; }
    Value getValue() const { return m_value; }
    void setValue(const Value& value) { m_value = value; }
    size_t getAccessCount() const { return m_accessCount; }
    void incrementAccessCount() { ++m_accessCount; }

private:
    Key m_key;
    Value m_value;
    size_t m_accessCount;  // 访问次数
};


/* ****************************************** LRU缓存 ****************************************** */
// 该缓存无锁
template<typename Key, typename Value>
class LruCache : public CachePolicy<Key, Value>
{
    using LruNodeType = LruNode<Key, Value>;
    // using NodePtr = std::shared_ptr<LruNodeType>; 
    using NodeIt = typename std::list<LruNodeType>::iterator;
    using CacheList = std::list<LruNodeType>;             // 缓存链
    using NodeMap = std::unordered_map<Key, NodeIt>;  // 从key映射到缓存链上的具体节点

public:  // 实现外部接口
    LruCache(int capacity)
    : m_capacity(capacity)
    { }

    ~LruCache() override = default;

    // 添加缓存
    void put(Key key, Value value) override
    {
        if (m_capacity <= 0)
            return;
    
        // std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_nodeMap.find(key);

        // key已经在缓存链表中
        if (it != m_nodeMap.end()) {
            // 更新value, 并调整该节点位置
            updateExistingNode(it->second, value);
            return ;
        }

        // 缓存链没有存满
        if (m_list.size() < m_capacity) {
            addNewNode(key, value);
        } else { // 淘汰最久未使用的节点，再添加新结点
            killLeastRecent();
            addNewNode(key, value);
        }
    }

    bool get(Key key, Value& value) override
    {
        // std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_nodeMap.find(key);
        if (it != m_nodeMap.end())
        {
            value = it->second->getValue();
            moveToMostRecent(it->second);
            return true;
        }
        return false;
    }

    Value get(Key key) override
    {
        Value value{};
        get(key, value);
        return value;
    }

    // 删除指定元素
    void remove(Key key) 
    {   
        // std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_nodeMap.find(key);
        if (it != m_nodeMap.end())
        {
            removeNode(it->second);
            m_nodeMap.erase(it);
        }
    }

    
    size_t getAccessCount(const Key& key)
    {
        // std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_nodeMap.find(key);
        if (it != m_nodeMap.end()) {
            return it->second->getAccessCount();
        }
        return 0;
    }

    void incrementAccessCount(const Key& key)
    {
        // std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_nodeMap.find(key);
        if (it != m_nodeMap.end()) {
            it->second->incrementAccessCount();
        }
    }

    size_t getSize()
    {
        return m_list.size();
    }

private: // 实现内部接口
    void updateExistingNode(NodeIt node, const Value& value) 
    {
        node->setValue(value);   // 更新value
        moveToMostRecent(node);  // 将节点移动到最新的位置
    }

    // 将新节点添加到链表尾部
    void addNewNode(const Key& key, const Value& value) 
    {
        m_list.push_back(LruNode{key, value});
        m_nodeMap[key] = --m_list.end();
    }

    // 将该节点移动到最新的位置 (链表尾)
    void moveToMostRecent(NodeIt node) 
    {
        if (node != --m_list.end()) {
            m_list.splice(m_list.end(), m_list, node);
        }
    }

    // 从链表中删除节点
    void removeNode(NodeIt node) 
    {
        m_list.erase(node);
    }

    // 驱逐最近最少访问 (链表头节点)
    void killLeastRecent() 
    {
        // 先根据key删除哈希表中对应记录
        m_nodeMap.erase(m_list.front().getKey());
        // 再删除链表头节点
        m_list.pop_front();
    }

private:
    int           m_capacity; // 缓存容量
    CacheList     m_list;     // 缓存链表：最近访问的元素放于链表尾，最久未访问的元素位于链表头
    NodeMap       m_nodeMap;  // key -> Node 
    // std::mutex    m_mutex;
};
